#include "maze.h"

void bit_set(u8* _BitArray, int _Size, int _Row, int _Col) {
    _BitArray[(_Row * _Size + _Col) / BITS_PER_BYTE] |= (1 << ((_Row * _Size + _Col) % BITS_PER_BYTE));
}

int bit_get(u8* _BitArray, int _Size, int _Row, int _Col) {
    return (_BitArray[(_Row * _Size + _Col) / BITS_PER_BYTE] >> ((_Row * _Size + _Col) % BITS_PER_BYTE)) & 1;
}

void bit_clear(u8* _BitArray, int _Size, int _Row, int _Col) {
    _BitArray[(_Row * _Size + _Col) / BITS_PER_BYTE] &= ~(1 << ((_Row * _Size + _Col) % BITS_PER_BYTE));
}

u8* maze_init(int _Size) {
    int _ByteSize = (_Size * _Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
    u8* _BitArray = (u8*)malloc(_ByteSize);
    if (_BitArray) {
        for (int row = 0; row < _Size; row++) {
            for (int col = 0; col < _Size; col++) {
                if (row % 2 == 0 || col % 2 == 0) {
                    bit_clear(_BitArray, _Size, row, col);
                }
                else {
                    bit_set(_BitArray, _Size, row, col);
                }
            }
        }
    }
    return _BitArray;
}

void maze_create(u8* _BitArray, int _Size, int _Row, int _Col) {
    // 目前先采取大位数组
    // 后续采用小数组
    int _ByteSize = (_Size * _Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
    int _size = _Size;
    u8* _VisitArray = (u8*)malloc(_ByteSize);

    maze_clear(_VisitArray, _Size);   // 全部初始化为 0

    bit_set(_VisitArray, _size, _Row, _Col);    // 设置初始位置为已探索
    create_dfs(_BitArray, _VisitArray, _Size, _Row, _Col);
}

void create_dfs(u8* _BitArray, u8* _VisitArray, int _Size, int _Row, int _Col) {
    // 是否输出迷宫构建过程
    int flag = 0;

    while (1) {
        // 判断是否无路可走
        if (is_have_road(_BitArray, _VisitArray, _Size, _Row, _Col) == 0) {
            break;
        }

        // 随机选一个方向
        int num = rand() % 4;
        switch (num)
        {
        case 0: // 上
            if (_Row >= 3 && bit_get(_VisitArray, _Size, _Row - 2, _Col) == ROAD) {
                bit_set(_BitArray, _Size, _Row - 1, _Col);   // 铺路
                bit_set(_VisitArray, _Size, _Row - 2, _Col);     // 已经访问
                if (flag) maze_show(_BitArray, _Size);
                create_dfs(_BitArray, _VisitArray, _Size, _Row - 2, _Col);  // 递归
            }
            break;
        case 1: // 下
            if (_Row <= _Size - 3 && bit_get(_VisitArray, _Size, _Row + 2, _Col) == ROAD) {
                bit_set(_BitArray, _Size, _Row + 1, _Col);   // 铺路
                bit_set(_VisitArray, _Size, _Row + 2, _Col);     // 已经访问
                if (flag) maze_show(_BitArray, _Size);
                create_dfs(_BitArray, _VisitArray, _Size, _Row + 2, _Col);  // 递归
            }
            break;
        case 2:  // 左
            if (_Col >= 3 && bit_get(_VisitArray, _Size, _Row, _Col - 2) == ROAD) {
                bit_set(_BitArray, _Size, _Row, _Col - 1);   // 铺路
                bit_set(_VisitArray, _Size, _Row, _Col - 2);     // 已经访问
                if (flag) maze_show(_BitArray, _Size);
                create_dfs(_BitArray, _VisitArray, _Size, _Row, _Col - 2);  // 递归
            }
            break;
        case 3:  // 右
            if (_Col <= _Size - 3 && bit_get(_VisitArray, _Size, _Row, _Col + 2) == ROAD) {
                bit_set(_BitArray, _Size, _Row, _Col + 1);   // 铺路
                bit_set(_VisitArray, _Size, _Row, _Col + 2);     // 已经访问
                if (flag) maze_show(_BitArray, _Size);
                create_dfs(_BitArray, _VisitArray, _Size, _Row, _Col + 2);  // 递归
            }
            break;
        }
    }
}

void maze_clear(u8* _BitArray, int _Size) {
    memset(_BitArray, 0, (_Size * _Size + BITS_PER_BYTE - 1) / BITS_PER_BYTE);
}

int is_have_road(u8* _BitArray, u8* _VisitArray, int _Size, int _Row, int _Col) {
    // 分别探索上、下、左、右
    if ((_Row >= 3 && bit_get(_VisitArray, _Size, _Row - 2, _Col) == ROAD)               // 上
        || (_Row <= _Size - 3 && bit_get(_VisitArray, _Size, _Row + 2, _Col) == ROAD)    // 下
        || (_Col >= 3 && bit_get(_VisitArray, _Size, _Row, _Col - 2) == ROAD)            // 左
        || (_Col <= _Size - 3 && bit_get(_VisitArray, _Size, _Row, _Col + 2) == ROAD))   // 右
    {
        return 1;
    }
    return 0;
}

void maze_show(u8* _BitArray, int _Size) {
    printf("\033[0;0H");
    int wall = 46, road = 47;
    for (int row = 0; row < _Size; row++) {
        for (int col = 0; col < _Size; col++) {
            if (bit_get(_BitArray, _Size, row, col) == 0)
                printf("\033[%dm  \033[0m", wall);
            else printf("\033[%dm  \033[0m", road);
        }
        printf("\033[0m\n");
    }
}

void maze_show_info(u8* _BitArray, int _Size) {
    printf("\033[s");
    printf("\033[2;3H\033[41m  \033[0m");
    printf("\033[%d;%dH\033[42m  \033[0m", _Size - 1, _Size * 2 - 3);
    printf("\033[u");
    printf("\n\033[46m  \033[0m: 墙壁\t\t\033[47m  \033[0m: 道路\t\t\033[41m  \033[0m: 起点\t\t\033[42m  \033[0m: 终点\n");

}

u8* maze_explore_around(u8* _BitArray, int _Size, int _Row, int _Col) {
    u8* _ret = (u8*)malloc(1);
    memset(_ret, 0, 4);

    if (bit_get(_BitArray, _Size, _Row - 1, _Col) == 1)
        bit_set(_ret, 1, 0, 0);
    if (bit_get(_BitArray, _Size, _Row + 1, _Col) == 1)
        bit_set(_ret, 1, 0, 1);
    if (bit_get(_BitArray, _Size, _Row, _Col - 1) == 1)
        bit_set(_ret, 1, 0, 2);
    if (bit_get(_BitArray, _Size, _Row, _Col + 1) == 1)
        bit_set(_ret, 1, 0, 3);

    return _ret;
}
